package com.cx.algrithm.sort;

import java.util.Arrays;

/**
 * @author shkstart
 * @date 7/22/2019 - 8:13 PM
 */
public class QuickSort {
    // 测试
    public static void main(String[] args) {
//        QuickSort s = new QuickSort();
        int[] arr = {11, 3, 29, 49, 30, 7, 50, 63, 46, 100, 99};
        System.out.println("排序前的数组: " + Arrays.toString(arr));
        quickSort2(arr, 0, arr.length - 1);
//        System.out.println(Arrays.toString(arr));
//        System.out.println("未排序的数组：" + Arrays.toString(arr));
//        s.quickSort1(arr, 0, arr.length-1);
//        // Resourse.quickSort2(arr, 0, arr.length - 1);
        System.out.println("排序后的数组：" + Arrays.toString(arr));
    }

    public static void quickSort1(int[] arr, int low, int high) {
        int base = arr[low];
        int start = low;
        int end = high;
        while (start < end) {
//            base是从地位开始，这里得首先从高位开始遍历
            while (start < end && base <= arr[end]) {
                end--;
            }
            if (base > arr[end]) {
                arr[start] = arr[end];
            }
            while (start < end && base >= arr[start]) {
                start++;
            }
            if (base < arr[start]) {
                arr[end] = arr[start];
            }
        }
        if (start == end) {
            arr[start] = base;
        }
        if (start > low) {
            quickSort1(arr, low, start - 1);
        }
        if (end < high) {
            quickSort1(arr, end + 1, high);
        }

    }

    public static void quickSort2(int[] arr, int low, int high) {
        int base = arr[low];
        int start = low;
        int end = high;
        while (start < end) {
            while (start < end && arr[end] >= base) {
                end--;
            }
            if (arr[end] < base) {
                arr[start] = arr[end];
            }
            while (start < end && arr[start] <= base) {
                start++;
            }
            if (arr[start] > base) {
                arr[end] = arr[start];
            }
        }
        if (start == end) {
            arr[start] = base;
        }
        if (start > low) {
            quickSort2(arr, low, start - 1);
        }
        if (end < high) {
            quickSort2(arr, end + 1, high);
        }

    }

    /**
     * 快速排序方法2
     */
    public int[] quickSort_m2(int[] array, int start, int end) {
        if (array.length < 1 || start < 0 || end >= array.length || start > end)
            return null;
        int smallIndex = partition(array, start, end);
        if (smallIndex > start)
            quickSort2(array, start, smallIndex - 1);
        if (smallIndex < end)
            quickSort2(array, smallIndex + 1, end);
        return array;
    }

    /**
     * 快速排序算法——partition
     */
    public int partition(int[] array, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        swap(array, pivot, end);
        for (int i = start; i <= end; i++)
            if (array[i] <= array[end]) {
                smallIndex++;
                if (i > smallIndex)
                    swap(array, i, smallIndex);
            }
        return smallIndex;
    }

    /**
     * 交换数组内两个元素
     */
    public void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


}

